{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Supply Network Design 1\n",
    "\n",
    "## Objective and Prerequisites\n",
    "\n",
    "Try this Jupyter Notebook Modeling Example to learn how to solve a classic supply network design problem that involves finding the minimum cost flow through a network. We’ll show you how – given a set of factories, depots, and customers – you can use mathematical optimization to determine the best way to satisfy customer demand while minimizing shipping costs.\n",
    "\n",
    "This model is example 19 from the fifth edition of Model Building in Mathematical Programming, by H. Paul Williams on pages 273-275 and 330-332.\n",
    "\n",
    "This example is of beginning difficulty; we assume that you know Python and have some knowledge of the Gurobi Python API and building mathematical optimization models.\n",
    "\n",
    "**Download the Repository** <br />\n",
    "You can download the repository containing this and other examples by clicking [here](https://github.com/Gurobi/modeling-examples/archive/master.zip). \n",
    "\n",
    "---\n",
    "## Problem Description\n",
    "\n",
    "In this problem, we have six end customers, each with a known demand for a product.  Customer demand can be satisfied from a set of four depots, or directly from a set of two factories.  Each depot can support a maximum volume of product moving through it, and each factory can produce a maximum amount of product.  There are known costs associated with transporting the product, from a factory to a depot, from a depot to a customer, or from a factory directly to a customer.\n",
    "\n",
    "Our supply network has two factories, in Liverpool and Brighton, that produce a product.  Each has a maximum production capacity:\n",
    "\n",
    "| Factory | Supply (tons) |\n",
    "| --- | --- |\n",
    "| Liverpool | 150,000 |\n",
    "| Brighton |  200,000 |\n",
    "\n",
    "The product can be shipped from a factory to a set of four depots.  Each depot has a maximum throughput.  Depots don't produce or consume the product; they simply pass the product on to customers.\n",
    "\n",
    "| Depot | Throughput (tons) |\n",
    "| --- | --- |\n",
    "| Newcastle | 70,000 |\n",
    "| Birmingham | 50,000 |\n",
    "| London | 100,000 |\n",
    "| Exeter | 40,000 |\n",
    "\n",
    "Our network has six customers, each with a given demand.\n",
    "\n",
    "| Customer | Demand (tons) |\n",
    "| --- | --- |\n",
    "| C1 | 50,000 |\n",
    "| C2 | 10,000 |\n",
    "| C3 | 40,000 |\n",
    "| C4 | 35,000 |\n",
    "| C5 | 60,000 |\n",
    "| C6 | 20,000 |\n",
    "\n",
    "Shipping costs are given in the following table (in dollars per ton).  Columns are source cities and rows are destination cities.  Thus, for example, it costs $1 per ton to ship the product from Liverpool to London.  A '-' in the table indicates that that combination is not possible, so for example it is not possible to ship from the factory in Brighton to the depot in Newcastle.\n",
    "\n",
    "| To | Liverpool | Brighton | Newcastle | Birmingham | London | Exeter |\n",
    "| --- | --- | --- | --- | --- | --- | --- |\n",
    "| Depots |\n",
    "| Newcastle  | 0.5 |   - |\n",
    "| Birmingham | 0.5 | 0.3 |\n",
    "| London     | 1.0 | 0.5 |\n",
    "| Exeter     | 0.2 | 0.2 |\n",
    "| Customers |\n",
    "| C1 | 1.0 | 2.0 |   - | 1.0 |   - |   - |\n",
    "| C2 |   - |   - | 1.5 | 0.5 | 1.5 |   - |\n",
    "| C3 | 1.5 |   - | 0.5 | 0.5 | 2.0 | 0.2 |\n",
    "| C4 | 2.0 |   - | 1.5 | 1.0 |   - | 1.5 |\n",
    "| C5 |   - |   - |   - | 0.5 | 0.5 | 0.5 |\n",
    "| C6 | 1.0 |   - | 1.0 |   - | 1.5 | 1.5 |\n",
    "\n",
    "The question to be answered is how to satisfy the demands of the end customers while minimizing shipping costs.\n",
    "\n",
    "---\n",
    "## Model Formulation\n",
    "\n",
    "### Sets and Indices\n",
    "\n",
    "$f \\in \\text{Factories}=\\{\\text{Liverpool}, \\text{Brighton}\\}$\n",
    "\n",
    "$d \\in \\text{Depots}=\\{\\text{Newcastle}, \\text{Birmingham}, \\text{London}, \\text{Exeter}\\}$\n",
    "\n",
    "$c \\in \\text{Customers}=\\{\\text{C1}, \\text{C2}, \\text{C3}, \\text{C4}, \\text{C5}, \\text{C6}\\}$\n",
    "\n",
    "$\\text{Cities} = \\text{Factories} \\cup \\text{Depots} \\cup \\text{Customers}$\n",
    "\n",
    "### Parameters\n",
    "\n",
    "$\\text{cost}_{s,t} \\in \\mathbb{R}^+$: Cost of shipping one ton from source $s$ to destination $t$.\n",
    "\n",
    "$\\text{supply}_f \\in \\mathbb{R}^+$: Maximum possible supply from factory $f$ (in tons).\n",
    "\n",
    "$\\text{through}_d \\in \\mathbb{R}^+$: Maximum possible flow through depot $d$ (in tons).\n",
    "\n",
    "$\\text{demand}_c \\in \\mathbb{R}^+$: Demand for goods at customer $c$ (in tons).\n",
    "\n",
    "### Decision Variables\n",
    "\n",
    "$\\text{flow}_{s,t} \\in \\mathbb{N}^+$: Quantity of goods (in tons) that is shipped from source $s$ to destionation $t$.\n",
    "\n",
    "\n",
    "### Objective Function\n",
    "\n",
    "- **Cost**: Minimize total shipping costs.\n",
    "\n",
    "\\begin{equation}\n",
    "\\text{Minimize} \\quad Z = \\sum_{(s,t) \\in \\text{Cities} \\times \\text{Cities}}{\\text{cost}_{s,t}*\\text{flow}_{s,t}}\n",
    "\\end{equation}\n",
    "\n",
    "### Constraints\n",
    "\n",
    "- **Factory output**: Flow of goods from a factory must respect maximum capacity.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{t \\in \\text{Cities}}{\\text{flow}_{f,t}} \\leq \\text{supply}_{f} \\quad \\forall f \\in \\text{Factories}\n",
    "\\end{equation}\n",
    "\n",
    "- **Customer demand**: Flow of goods must meet customer demand.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{s \\in \\text{Cities}}{\\text{flow}_{s,c}} = \\text{demand}_{c} \\quad \\forall c \\in \\text{Customers}\n",
    "\\end{equation}\n",
    "\n",
    "- **Depot flow**: Flow into a depot equals flow out of the depot.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{s \\in \\text{Cities}}{\\text{flow}_{s,d}} = \n",
    "\\sum_{t \\in \\text{Cities}}{\\text{flow}_{d,t}}\n",
    "\\quad \\forall d \\in \\text{Depots}\n",
    "\\end{equation}\n",
    "\n",
    "- **Depot capacity**: Flow into a depot must respect depot capacity.\n",
    "\n",
    "\\begin{equation}\n",
    "\\sum_{s \\in \\text{Cities}}{\\text{flow}_{s,d}} \\leq \\text{through}_{d}\n",
    "\\quad \\forall d \\in \\text{Depots}\n",
    "\\end{equation}\n",
    "\n",
    "---\n",
    "## Python Implementation\n",
    "\n",
    "We import the Gurobi Python Module and other Python libraries."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "%pip install gurobipy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import pandas as pd\n",
    "\n",
    "import gurobipy as gp\n",
    "from gurobipy import GRB\n",
    "\n",
    "# tested with Python 3.11 & Gurobi 11.0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Input Data\n",
    "We define all the input data for the model."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Create dictionaries to capture factory supply limits, depot throughput limits, and customer demand.\n",
    "\n",
    "supply = dict({'Liverpool': 150000,\n",
    "               'Brighton': 200000})\n",
    "\n",
    "through = dict({'Newcastle': 70000,\n",
    "                'Birmingham': 50000,\n",
    "                'London': 100000,\n",
    "                'Exeter': 40000})\n",
    "\n",
    "demand = dict({'C1': 50000,\n",
    "               'C2': 10000,\n",
    "               'C3': 40000,\n",
    "               'C4': 35000,\n",
    "               'C5': 60000,\n",
    "               'C6': 20000})\n",
    "\n",
    "# Create a dictionary to capture shipping costs.\n",
    "\n",
    "arcs, cost = gp.multidict({\n",
    "    ('Liverpool', 'Newcastle'): 0.5,\n",
    "    ('Liverpool', 'Birmingham'): 0.5,\n",
    "    ('Liverpool', 'London'): 1.0,\n",
    "    ('Liverpool', 'Exeter'): 0.2,\n",
    "    ('Liverpool', 'C1'): 1.0,\n",
    "    ('Liverpool', 'C3'): 1.5,\n",
    "    ('Liverpool', 'C4'): 2.0,\n",
    "    ('Liverpool', 'C6'): 1.0,\n",
    "    ('Brighton', 'Birmingham'): 0.3,\n",
    "    ('Brighton', 'London'): 0.5,\n",
    "    ('Brighton', 'Exeter'): 0.2,\n",
    "    ('Brighton', 'C1'): 2.0,\n",
    "    ('Newcastle', 'C2'): 1.5,\n",
    "    ('Newcastle', 'C3'): 0.5,\n",
    "    ('Newcastle', 'C5'): 1.5,\n",
    "    ('Newcastle', 'C6'): 1.0,\n",
    "    ('Birmingham', 'C1'): 1.0,\n",
    "    ('Birmingham', 'C2'): 0.5,\n",
    "    ('Birmingham', 'C3'): 0.5,\n",
    "    ('Birmingham', 'C4'): 1.0,\n",
    "    ('Birmingham', 'C5'): 0.5,\n",
    "    ('London', 'C2'): 1.5,\n",
    "    ('London', 'C3'): 2.0,\n",
    "    ('London', 'C5'): 0.5,\n",
    "    ('London', 'C6'): 1.5,\n",
    "    ('Exeter', 'C3'): 0.2,\n",
    "    ('Exeter', 'C4'): 1.5,\n",
    "    ('Exeter', 'C5'): 0.5,\n",
    "    ('Exeter', 'C6'): 1.5\n",
    "})"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Model Deployment\n",
    "\n",
    "We create a model and the variables. The variables simply capture the amount of product that flows along each allowed path between a source and destination.  Objective coefficients are provided here (in $\\text{cost}$) , so we don't need to provide an optimization objective later."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Using license file c:\\gurobi\\gurobi.lic\n"
     ]
    }
   ],
   "source": [
    "model = gp.Model('SupplyNetworkDesign')\n",
    "flow = model.addVars(arcs, obj=cost, name=\"flow\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our first constraints require the total flow along arcs leaving a factory to be at most as large as the supply capacity of that factory."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Production capacity limits\n",
    "\n",
    "factories = supply.keys()\n",
    "factory_flow = model.addConstrs((gp.quicksum(flow.select(factory, '*')) <= supply[factory]\n",
    "                                 for factory in factories), name=\"factory\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our next constraints require the total flow along arcs entering a customer to be equal to the demand from that customer."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Customer demand\n",
    "\n",
    "customers = demand.keys()\n",
    "customer_flow = model.addConstrs((gp.quicksum(flow.select('*', customer)) == demand[customer]\n",
    "                                  for customer in customers), name=\"customer\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Our final constraints relate to depots.  The first constraints require that the total amount of product entering the depot must equal the total amount leaving."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Depot flow conservation\n",
    "\n",
    "depots = through.keys()\n",
    "depot_flow = model.addConstrs((gp.quicksum(flow.select(depot, '*')) == gp.quicksum(flow.select('*', depot))\n",
    "                               for depot in depots), name=\"depot\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The second set limits the product passing through the depot to be at most equal the throughput of that deport."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Depot throughput\n",
    "\n",
    "depot_capacity = model.addConstrs((gp.quicksum(flow.select('*', depot)) <= through[depot]\n",
    "                                   for depot in depots), name=\"depot_capacity\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now optimize the model"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Gurobi Optimizer version 9.1.0 build v9.1.0rc0 (win64)\n",
      "Thread count: 4 physical cores, 8 logical processors, using up to 8 threads\n",
      "Optimize a model with 16 rows, 29 columns and 65 nonzeros\n",
      "Model fingerprint: 0x3607c855\n",
      "Coefficient statistics:\n",
      "  Matrix range     [1e+00, 1e+00]\n",
      "  Objective range  [2e-01, 2e+00]\n",
      "  Bounds range     [0e+00, 0e+00]\n",
      "  RHS range        [1e+04, 2e+05]\n",
      "Presolve removed 1 rows and 0 columns\n",
      "Presolve time: 0.03s\n",
      "Presolved: 15 rows, 29 columns, 64 nonzeros\n",
      "\n",
      "Iteration    Objective       Primal Inf.    Dual Inf.      Time\n",
      "       0    1.4800000e+05   1.812500e+04   0.000000e+00      0s\n",
      "       7    1.9850000e+05   0.000000e+00   0.000000e+00      0s\n",
      "\n",
      "Solved in 7 iterations and 0.03 seconds\n",
      "Optimal objective  1.985000000e+05\n"
     ]
    }
   ],
   "source": [
    "model.optimize()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## Analysis\n",
    "\n",
    "Product demand from all of our customers can be satisfied for a total cost of $\\$198,500$. The optimal plan is as follows."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<div>\n",
       "<style scoped>\n",
       "    .dataframe tbody tr th:only-of-type {\n",
       "        vertical-align: middle;\n",
       "    }\n",
       "\n",
       "    .dataframe tbody tr th {\n",
       "        vertical-align: top;\n",
       "    }\n",
       "\n",
       "    .dataframe thead th {\n",
       "        text-align: right;\n",
       "    }\n",
       "</style>\n",
       "<table border=\"1\" class=\"dataframe\">\n",
       "  <thead>\n",
       "    <tr style=\"text-align: right;\">\n",
       "      <th></th>\n",
       "      <th>From</th>\n",
       "      <th>To</th>\n",
       "      <th>Flow</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Liverpool</td>\n",
       "      <td>C1</td>\n",
       "      <td>50000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Liverpool</td>\n",
       "      <td>C6</td>\n",
       "      <td>20000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Brighton</td>\n",
       "      <td>Birmingham</td>\n",
       "      <td>50000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Brighton</td>\n",
       "      <td>London</td>\n",
       "      <td>55000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Brighton</td>\n",
       "      <td>Exeter</td>\n",
       "      <td>40000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Birmingham</td>\n",
       "      <td>C2</td>\n",
       "      <td>10000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Birmingham</td>\n",
       "      <td>C4</td>\n",
       "      <td>35000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Birmingham</td>\n",
       "      <td>C5</td>\n",
       "      <td>5000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>London</td>\n",
       "      <td>C5</td>\n",
       "      <td>55000.0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th></th>\n",
       "      <td>Exeter</td>\n",
       "      <td>C3</td>\n",
       "      <td>40000.0</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n",
       "</div>"
      ],
      "text/plain": [
       "        From          To     Flow\n",
       "   Liverpool          C1  50000.0\n",
       "   Liverpool          C6  20000.0\n",
       "    Brighton  Birmingham  50000.0\n",
       "    Brighton      London  55000.0\n",
       "    Brighton      Exeter  40000.0\n",
       "  Birmingham          C2  10000.0\n",
       "  Birmingham          C4  35000.0\n",
       "  Birmingham          C5   5000.0\n",
       "      London          C5  55000.0\n",
       "      Exeter          C3  40000.0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "product_flow = pd.DataFrame(\n",
    "    [{\"From\": arc[0], \"To\": arc[1], \"Flow\": flow[arc].x} for arc in arcs if flow[arc].x > 1e-6]\n",
    ")\n",
    "product_flow.index=[''] * len(product_flow)\n",
    "product_flow"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---\n",
    "## References\n",
    "\n",
    "H. Paul Williams, Model Building in Mathematical Programming, fifth edition.\n",
    "\n",
    "Copyright © 2020 Gurobi Optimization, LLC"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
